/*
 * Licensed to GraphHopper GmbH under one or more contributor
 * license agreements. See the NOTICE file distributed with this work for
 * additional information regarding copyright ownership.
 *
 * GraphHopper GmbH licenses this file to you under the Apache License,
 * Version 2.0 (the "License"); you may not use this file except in
 * compliance with the License. You may obtain a copy of the License at
 *
 *       http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package com.graphhopper.jsprit.core.algorithm.ruin;

import com.graphhopper.jsprit.core.algorithm.listener.IterationStartsListener;
import com.graphhopper.jsprit.core.problem.VehicleRoutingProblem;
import com.graphhopper.jsprit.core.problem.job.Job;
import com.graphhopper.jsprit.core.problem.solution.VehicleRoutingProblemSolution;
import com.graphhopper.jsprit.core.problem.solution.route.VehicleRoute;
import com.graphhopper.jsprit.core.problem.solution.route.activity.TourActivity;
import com.graphhopper.jsprit.core.util.RandomUtils;
import org.apache.commons.math3.ml.clustering.Clusterable;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.util.*;
import java.util.stream.Collectors;


/**
 * Ruin strategy that ruins current solution randomly. I.e.
 * customer are removed randomly from current solution.
 * 破坏策略，随机破坏当前的解。即：随机移除
 *
 * @author stefan schroeder
 */

public final class RuinClusters extends AbstractRuinStrategy implements IterationStartsListener {

    @Override
    public void informIterationStarts(int i, VehicleRoutingProblem problem, Collection<VehicleRoutingProblemSolution> solutions) {
        minPts = 1 + random.nextInt(2);
        epsFactor = 0.5 + random.nextDouble();
    }

    public static class JobActivityWrapper implements Clusterable {

        private TourActivity.JobActivity jobActivity;

        public JobActivityWrapper(TourActivity.JobActivity jobActivity) {
            this.jobActivity = jobActivity;
        }

        @Override
        public double[] getPoint() {
            return new double[]{jobActivity.getLocation().getCoordinate().getX(), jobActivity.getLocation().getCoordinate().getY()};
        }

        public TourActivity.JobActivity getActivity() {
            return jobActivity;
        }
    }

    private Logger logger = LoggerFactory.getLogger(RuinClusters.class);

    private VehicleRoutingProblem vrp;


    private JobNeighborhoods jobNeighborhoods;

    private int noClusters = 2;
    /**
     * 最小的点的个数
     */
    private int minPts = 1;
    /**
     * epsilon因子
     */
    private double epsFactor = 0.8;

    public RuinClusters(VehicleRoutingProblem vrp, final int initialNumberJobsToRemove, JobNeighborhoods jobNeighborhoods) {
        super(vrp);
        this.vrp = vrp;
        setRuinShareFactory(() -> initialNumberJobsToRemove);
        this.jobNeighborhoods = jobNeighborhoods;
        logger.debug("initialise {}", this);
    }

    public void setNoClusters(int noClusters) {
        this.noClusters = noClusters;
    }

    /**
     * Removes a fraction of jobs from vehicleRoutes.
     * 从车辆路径中移除一小部分任务
     * <p>
     * <p>The number of jobs is calculated as follows: Math.ceil(vrp.getJobs().values().size() * fractionOfAllNodes2beRuined).
     * Math.ceil：向上取整
     * 任务数量计算如下：Math.ceil(vrp.getJobs().values().size() * fractionOfAllNodes2beRuined).
     */
    @Override
    public Collection<Job> ruinRoutes(Collection<VehicleRoute> vehicleRoutes) {
        List<Job> unassignedJobs = new ArrayList<>();
        //1 获取需要移除的任务数
        int nOfJobs2BeRemoved = getRuinShareFactory().createNumberToBeRemoved();
        ruin(vehicleRoutes, nOfJobs2BeRemoved, unassignedJobs);
        return unassignedJobs;
    }

    private void ruin(Collection<VehicleRoute> vehicleRoutes, int nOfJobs2BeRemoved, List<Job> unassignedJobs) {
        //1 没有任务则终止
        if (vrp.getJobs().values().size() == 0) {
            return;
        }

        //2 初始化变量
        //2.1 任务和其所在的路线
        Map<Job, VehicleRoute> mappedRoutes = map(vehicleRoutes);
        //2.2 待移除的任务数
        int toRemove = nOfJobs2BeRemoved;
        //2.3 最近移除的任务集合
        Collection<Job> lastRemoved = new ArrayList<>();
        //2.4 已破坏的路线集合
        Set<VehicleRoute> ruined = new HashSet<>();
        //2.5 移除的任务集合
        Set<Job> removed = new HashSet<>();
        //2.6 循环的候选路线
        Set<VehicleRoute> cycleCandidates = new HashSet<>();

        //3 遍历
        while (toRemove > 0) {
            Job target;
            //3.0 待删除的路线
            VehicleRoute targetRoute = null;
            //3.1 如果最近删除的任务集合为空，这里假设为第一次进来的时候
            if (lastRemoved.isEmpty()) {
                //3.1.1 随机选择一个任务
                target = RandomUtils.nextJob(vrp.getJobs().values(), random);
                //3.1.2 获取该任务的车辆路线
                targetRoute = mappedRoutes.get(target);
            }
            //3.2 如果最近删除集合不为空
            else {
                //3.2.1 在最近删除的任务集合中随机选择一个任务
                target = RandomUtils.nextJob(lastRemoved, random);
                //3.2.2 获取该任务的邻结点，距离排序(从小到大)
                Iterator<Job> neighborIterator = jobNeighborhoods.getNearestNeighborsIterator(nOfJobs2BeRemoved, target);
                while (neighborIterator.hasNext()) {
                    Job j = neighborIterator.next();
                    //3.2.3 如果邻结点任务和路线都没有被删除
                    if (!removed.contains(j) && !ruined.contains(mappedRoutes.get(j))) {
                        targetRoute = mappedRoutes.get(j);
                        break;
                    }
                }
                lastRemoved.clear();
            }
            if (targetRoute == null) {
                break;
            }
            if (cycleCandidates.contains(targetRoute)) {
                break;
            }
            if (ruined.contains(targetRoute)) {
                cycleCandidates.add(targetRoute);
                break;
            }
            DBSCANClusterer dbscan = new DBSCANClusterer(vrp.getTransportCosts());
            dbscan.setRandom(random);
            dbscan.setMinPts(minPts);
            dbscan.setEpsFactor(epsFactor);
            //通过[密度聚类算法]
            //1 创建一个集群
            //2 随机获取一个集群点
            //3 获取该集群点的所有任务集合
            List<Job> cluster = dbscan.getRandomCluster(targetRoute);
            for (Job j : cluster) {
                if (toRemove == 0) {
                    break;
                }
                //移除任务
                if (removeJob(j, vehicleRoutes)) {
                    lastRemoved.add(j);
                    unassignedJobs.add(j);
                }
                toRemove--;
            }
            ruined.add(targetRoute);
        }
    }

    private List<JobActivityWrapper> wrap(List<TourActivity> activities) {
        return activities.stream()
            .map(activity -> new JobActivityWrapper((TourActivity.JobActivity) activity))
            .collect(Collectors.toList());
    }

    private Map<Job, VehicleRoute> map(Collection<VehicleRoute> vehicleRoutes) {
        Map<Job, VehicleRoute> map = new HashMap<>(vrp.getJobs().size());
        for (
            VehicleRoute route : vehicleRoutes) {
            for (Job job : route.getTourActivities().getJobs()) {
                map.put(job, route);
            }
        }
        return map;
    }

    @Override
    public String toString() {
        return "[name=clusterRuin]";
    }

}
